/*
 * 	S-EXPRESSIONS - Efficient representation of structured data.
 * 
 *  Copyright 2011 Jason Feingold
 *
 *  Licensed under the Apache License, Version 2.0 (the "License")
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */
/*
 * S-Expressions
 * Inspired by http://people.csail.mit.edu/rivest/Sexp.txt
 * 
 * A nice feature of s-expressions is that they can be parsed with a single character look ahead.
 * 
 * Only supports c-style strings, tokens, and, of course, length prefixed atoms.
 * Tokens are more liberal about which chars they can contain.
 * Hex and octal embeds in strings are not supported.
 * Display hints are not supported.
 * List delimiters are brackets rather than parentheses.
 */
package sexpr

/**
 * Values in an s-expression
 */
abstract class SExpr
{
	def isList : Boolean
	def isAtom : Boolean
	def toList : SList = sys error "Expression is not a list."
	def toAtom : SAtom = sys error "Expression is not an atom."
	override def toString = SExpr write this
}
/**
 * Atoms are data (i.e. strings of chars). May be zero length.
 */
case class SAtom (val s : String) extends SExpr
{
	if (null == s) throw new NullPointerException ("atom's value cannot be null.")
	override def isList = false
	override def isAtom = true
	override def toAtom = this
}
/**
 * Lists of s-expressions.  Each item in the list is a atom or a list. May be zero length.
 */
case class SList (val items : List [SExpr]) extends SExpr
{
	if (null == items) throw new NullPointerException ("list's contents cannot be null.")
	override def isList = true
	override def isAtom = false
	override def toList = this
}

/**
 * Auxiliary methods and types for S-expressions.
 */
object SExpr
{
	type Pos = (Int, Int)
	/**
	 * Tracks the position of the source when reading.
	 */
	class SourcePos
	{
		private var column_ = 1
		private var line_ = 1
		private def incColumn = column_ += 1
		private def incLine = { column_ = 1 ; line_ += 1 }
		def column = column_
		def line = line_
		/**
		 * @param c Tell it which char you've just taken and it tells you where you are!
		 */
		def mark (c : Char)
		{
			if ('\n' == c) incLine else incColumn
		}
		def pos = (line_, column_)
	}
	
	class ParseException (msg : String, cause : Throwable) extends Exception (msg, cause)
	{
		def this (msg : String) = this (msg, null)
	}
	
	/**
	 * Adapter for char streams to be used as sources for the reader.
	 */
	trait ReaderSource
	{
		/**
		 * Get a single char from the stream or throw.
		 */
		protected [this] def get : Char
		private val sourcePos = new SourcePos
		private var buffer : Option [Char] = None
		/**
		 * @return The next char in the source stream without extraction. May cause EOF.
		 */
		def peek : Char =
		{
			buffer match
			{
			case None => 
				val c = get
				buffer = Some (c)
				return c
			case Some (c) => c
			}
		}
		/**
		 * @return The next char in the source stream with extraction. May cause EOF.
		 */
		def take : Char =
		{
			val c = buffer match
			{
			case None => get
			case Some (c) => buffer = None ; c
			}
			sourcePos mark c
			return c
		}
		/**
		 * @return The current position in the source stream as (line, column).
		 */
		def pos = sourcePos.pos
		/**
		 * Consume all the whitespace at the front of the stream.
		 */
		def eatWhite : Unit = if (peek.isWhitespace) { take ; eatWhite }
	}
	/**
	 * For when you want to parse a string.
	 */
	class ReaderString (s : String) extends ReaderSource
	{
		private var index = -1
		override protected [this] def get : Char = { index += 1 ; s charAt index }
	}
	/**
	 * For when you want to parse from a stream.
	 */
	class ReaderStream (s : java.io.InputStream) extends ReaderSource
	{
		override protected [this] def get : Char = 
		{
			val c = s.read
			if (0 > c) throw new java.io.EOFException ("EOF")
			return c.asInstanceOf [Char]
		 }
	}
	/**
	 * Adapter for consuming chars from the writer. 
	 */
	trait WriterSink
	{
		def << (c : Char) : WriterSink
		def << (s : String) : WriterSink = { for (c <- s) this << c ; this }
	}
	class WriterStringBuilder (val s : StringBuilder) extends WriterSink
	{
		def this () = this (new StringBuilder)
		override def << (c : Char) = { s append c ; this }
	}
	class WriterStream (val s : java.io.OutputStream) extends WriterSink
	{
		override def << (c : Char) = { s write c ; this }
	}
	def read (s : ReaderSource, b : Builder) = new Reader (s, b).read
	def read (s : ReaderSource) : SExpr = 
	{
		val builder = new BuilderReify
		new Reader (s, builder).read
		builder.expr
	}
	def read (s : String) : SExpr = read (new ReaderString (s))
	def read (s : java.io.InputStream) : SExpr = read (new ReaderStream (s))
	/**
	 * Emits in canonical form: no whitespace outside atoms, all atoms in length prefixed form.
	 * @param x What to write.
	 * @param s Where to write it.
	 */
	def write (x : SExpr, s : WriterSink) : Unit =
	{
		 x match
		 {
		 case SAtom (d) => 
			 s << ("" + d.length) << ':' << d
		 case SList (xs) => 
			 s << "["
			 for (x <- xs) write (x, s)
			 s << "]"
		 }
	}
	def write (x : SExpr) : String = 
	{
		val s = new WriterStringBuilder
		write (x, s)
		return s.s.toString
	}
	def write (x : SExpr, s : StringBuilder) : Unit = write (x, new WriterStringBuilder (s))
	def write (x : SExpr, s : java.io.OutputStream) : Unit = write (x, new WriterStream (s))
	
	class Writer (sink : WriterSink, istring : String = "\t")
	{
		def this (ostream : java.io.OutputStream) = this (new WriterStream (ostream))
		private var indentLevel = 0
		/**
		 * Insert a new line and a number of tabs equal to the list nesting level.
		 */
		def indent : Writer = 
		{ 
			sink << '\n'
			for (i <- 0 until indentLevel) sink << istring
			this
		}
		/**
		 * Begin a list.
		 */
		def start (autoIndent : Boolean = false) : Writer = 
		{
			if (autoIndent) indent
			sink << '['
			indentLevel += 1
			this
		}
		/**
		 * End a list.
		 */
		def end (autoIndent : Boolean = false) : Writer = 
		{
			indentLevel -= 1
			if (autoIndent) indent
			sink << ']'
			this
		}
		/**
		 * Writes a run length encoded atom.
		 */
		def atom (s : String, autoIndent : Boolean = false) : Writer = 
		{
			if (autoIndent) indent
			sink << ("" + s.length) << ':' << s
			this
		}
		/**
		 * Writes an atom as a token.  If it's not a token you'll get the wrong s-expression.
		 */
		def token (s : String, autoIndent : Boolean = false) : Writer = 
		{
			if (autoIndent) indent
			sink << s
			this
		}
		/**
		 * Writes an atom as a c-string.  This will escape chars as it writes them.
		 */
		def string (s : String, autoIndent : Boolean = false) : Writer =
		{
			if (autoIndent) indent
			sink << '\"'
			for (c <- s)
			{
				c match
				{
					case '\t' => sink << "\\t"
					case '\r' => sink << "\\r"
					case '\n' => sink << "\\n"
					case '\\' => sink << "\\\\"
					case x => sink << x
				}
			}
			sink << '\"'
			this
		}
		/**
		 * Inserts spaces into the text.
		 */
		def spaces (i : Int) : Writer = 
		{
			for (q <- 0 until i) sink << ' '
			this
		}
	}
	/**
	 * Constructs S-Expressions.
	 * This can be used as a SAX like consumer (esp. for parses of large files).
	 * You can also use it to construct your own on the fly.
	 */
	abstract trait Builder
	{
		/**
		 * Start a list.
		 */
		def start (pos : Pos)
		/**
		 * End a list.
		 */
		def end (pos : Pos)
		/**
		 * Create an atom.
		 */
		def atom (pos : Pos, s : String)
	}
	/**
	 * Builds the full, in memory, s-expression.
	 */
	class BuilderReify extends Builder
	{
		import scala.collection.mutable.Stack
		/**
		 * Keeps track of where lists are opened so that we can report where unclosed lists started.
		 */
		private val lists = new Stack [Pos]
		/**
		 * The stack of lists being built.
		 * We seed it with an empty that, at the end of a correct parse, will contain a single list.
		 */
		private val stack = new Stack [Stack [SExpr]] push (new Stack)
		/**
		 * starts a new list by pushing a new empty stack
		 */
		override def start (pos : Pos) = { lists push pos ; stack push (new Stack) }
		/**
		 * ends a list by removing the top of the stack, making a list out of it, and pushing the new list
		 * to the next thing on the stack.
		 * The lambda here forces stack.pop to be evaluated before stack.top.
		 */
		override def end (pos : Pos) = { lists.pop ; ((list : SList) => stack.top push (list)) (SList (stack.pop.toList.reverse)) }
		/**
		 * Adds an atom to the list currently being constructed.
		 */
		override def atom (pos : Pos, s : String) = stack.top.push (SAtom (s))
		/**
		 * @return The expression built.
		 */
		def expr : SList =
		{
			if (! lists.isEmpty) sys error ("Unclosed list starting at: " + lists.pop)
			if (1 != stack.size) sys error ("Incorrect parse: stack " + stack.size + "\n" + stack.toString)
			val b = stack.pop
			if (1 != b.size) sys error ("Incorrect parse: top " + b.size + "\n" + stack.toString)
			b.pop match
			{
			case x : SList => x
			case _ => sys error "Bottom is an atom: should be a list."
			}
		}
	}
	/**
	 * Static auxiliaries for Reader.
	 */
	private object Reader
	{
		// chars other than letters and digits that can appear after the first char in an id.
		private val idChars = ",.;:`~!@#$%^&*|=+/?-_"
		// chars other than letters and digits and the escape char that are allowed in strings.
		private val stringChars = ",.<>;:`~!@#$%^&*(){}[]|=+/?-_ "
		private def isValidStringChar (c : Char) = c.isLetterOrDigit || (stringChars contains c)
		private def isValidTokenInitial (c : Char) = c.isLetter || (idChars contains c)
		private def isValidTokenMedial (c : Char) = c.isLetterOrDigit || (idChars contains c)
	}
	private class Reader (source : ReaderSource, builder : Builder)
	{
		import Reader._
		private var commentLevel = 0
		private def checkEOF (f : => Char) : Char =
		{
			try { f }
			catch
			{
			case e => parseError ("Unexpected EOF.")
			}
		}
		private def peek = checkEOF (source.peek)
		private def take = checkEOF (source.take)
		private def eatWhite = source.eatWhite
		private def parseError (msg : String) = throw new ParseException ("Parse error at " + source.pos + ": " + msg, null)
		def read { parseList ; builder }
		private def parseList
		{
			// eatWhite
			val c = take
			if (c != '[')
				sys error ("Expected '[' got '" + c + "'")
			if (0 == commentLevel) builder start source.pos
			parseItems
		}
		private def parseItems
		{
			def parseIt
			{
				eatWhite
				val c = peek
				if (c == ']') { take ; if (0 == commentLevel) builder end source.pos ; return }
				else if (c == '[') parseList
				else if (c == '<') { take ; commentLevel += 1 }
				else if (c == '>')
				{
					if (0 == commentLevel) parseError ("Invalid end of comment.")
					take ; commentLevel -= 1
				}
				else if (c == '{') parseBase64
				else if (c == '"') parseString
				else if (isValidTokenInitial (c)) parseToken
				else if (c.isDigit) parsePrefix
				else parseError ("Unexpected char: " + c) 
				parseIt
			}
			parseIt
		}
		private def parsePrefix
		{
			def parseLength (s : StringBuilder) : Int =
			{
				val c = take
				if (c.isDigit) { return parseLength (s append c)}
				else if (':' == c) return Integer parseInt s.toString
				else sys error ("Unexpected char: " + c)
			}
			if (! peek.isDigit)
				sys error ("Invalid start for prefixed atom: " + peek)
			val s = new StringBuilder
			val length = parseLength ((new StringBuilder) append take)
			for (i <- 0 until length)
				s append take
			if (0 == commentLevel) builder atom (source.pos, s.toString)
		}
		private def parseToken
		{
			val s = new StringBuilder
			if (! isValidTokenInitial (peek))
				sys error ("Invalid char at start of token: " + peek)
			s append take
			def parseIt { if (isValidTokenMedial (peek)) { s append take ; parseIt } }
			parseIt
			if (0 == commentLevel) builder atom (source.pos, s.toString)
		}
		private def halfNibble (c : Char) : Int =
		{
			c.toLower match
			{
			case '0' => 0
			case '1' => 1
			case '2' => 2
			case '3' => 3
			case '4' => 4
			case '5' => 5
			case '6' => 6
			case '7' => 7
			case '8' => 8
			case '9' => 9
			case 'a' => 10
			case 'b' => 11
			case 'c' => 12
			case 'd' => 13
			case 'e' => 14
			case 'f' => 15
			case _ => parseError ("Invalid hex character: " + c)
			}
		}
		private def parseBase64
		{
			val s = new StringBuilder
			def parseIt : Array [Byte] =
			{
				val c = take
				if ('}' == c) javax.xml.bind.DatatypeConverter.parseBase64Binary(s.toString)
				else { s += c ; parseIt }
			}
			new String (parseIt)
		}
		private def parseString
		{
			val s = new StringBuilder
			def parseEscape
			{
				val c = take
				if ('"' == c) s append '"'
				else if ('\\' == c) s append '\\'
				else if ('t' == c) s append '\t'
				else if ('n' == c) s append '\n'
				else if ('r' == c) s append '\r'
				else if ('x' == c)
					s append (16 * halfNibble (take) + halfNibble (take)).asInstanceOf [Char]
				else sys error ("Illegal escape char: " + c)
			}
			def parseIt
			{
				val c = take
				if (c == '"') return
				else if (isValidStringChar (c))
				{
					s append c ; parseIt
				}
				else if (c == '\\')
				{
					parseEscape ; parseIt
				}
				else sys error ("Illegal char: " + c)
			}
			val c = take
			if (c != '"') sys error "Expected '\"'"
			parseIt
			if (0 == commentLevel) builder atom (source.pos, s.toString)
		}
	}
}
